package leetcode.code0403;

/**
 * 从这出发能去哪 <br>
 * 递归可以 dp不行
 *
 * @author CaoYu
 * @date 2021年10月5日
 * @description
 */
public class Solution1 extends Solution403 {

	@Override
	public boolean canCross(int[] stones) {
		if (stones[1] != 1)
			return false;
		return this.canCross(stones, 1, 1);
	}

	/**
	 * 上一步是k, 现在站在stone上, 能不能跳到最后
	 *
	 * @param stones
	 * @param stone
	 * @param k
	 * @return
	 */
	private boolean canCross(int[] stones, int stone, int k) {
		if (stone == stones.length - 1)
			return true;
		for (int i = stone + 1; i < stones.length; i++) {
			for (int j = k - 1; j <= k + 1; j++) {
				if (stones[i] == stones[stone] + j) {
					boolean can = this.canCross(stones, i, j);
					if (can)
						return true;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		so.debug2();
	}

}
